package easy;

import util.PrintUtils;

import java.util.ArrayList;
import java.util.List;

public class Solution_1636 {
    public int[] frequencySort(int[] nums) {
        int[] counts = new int[201];
        for (int num : nums) {
            counts[num + 100]++;
        }

        List<Integer>[] sorts = new List[101];
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0) {
                List<Integer> sort = sorts[counts[i]];
                if (sort == null) {
                    sort = new ArrayList<>();
                }
                sort.add(i - 100);
                sorts[counts[i]] = sort;
            }
        }
        int index = 0;
        for (int i = 0; i < sorts.length; i++) {
            if (sorts[i] != null) {
                List<Integer> sort = sorts[i];
                sort.sort((a, b) -> b - a);
                for (Integer integer : sort) {
                    for (int j = 0; j < i; j++) {
                        nums[index++] = integer;
                    }
                }
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        Solution_1636 model = new Solution_1636();
        PrintUtils.arrayInt(model.frequencySort(new int[]{1, 5, 0, 5}));
        PrintUtils.arrayInt(model.frequencySort(new int[]{1, 1, 2, 2, 2, 3}));
        PrintUtils.arrayInt(model.frequencySort(new int[]{2, 3, 1, 3, 2}));
        PrintUtils.arrayInt(model.frequencySort(new int[]{-1,1,-6,4,5,-6,1,4,1}));
    }
}
